www.gusucode.com > C++ 各种排序算法演示(插入、希尔、冒泡、快速等)-源码程序 > C++ 各种排序算法演示(插入、希尔、冒泡、快速等)-源码程序/code/QuickSort/main.cpp

    //Download by http://www.NewXing.com
#include<iostream>
#include<ctime>
using namespace std;

//数组的第一个元素就不参与到排序中，即测试数据的第一个记录不参与排序
//为数组的第一个元素r[0]留作他用

//快速排序
//快速排序一次划分函数
int compare(0),move(0);
int Partition(int r[],int low,int high)
{
	
	r[0]=r[low];
	while(low<high)
	{
	
		while(low<high&&r[high]>=r[0])
		{
			--high;	
			compare++;
		}
		r[low]=r[high];
		move++;

		while(low<high&&r[low]<=r[0])
		{
			++low;	
			compare++;
		}
		r[high]=r[low];
		move++;
	}
	r[low]=r[0];
	return low;
}
//快速排序递归函数
void QuickSort(int r[],int first,int end)
{
	int pivot;
	if(first<end)
	{
		pivot=Partition(r,first,end);
		QuickSort(r,first,pivot-1);
		QuickSort(r,pivot+1,end);
	}
}



void main()
{
	int i;

	cout<<"快速排序测试:"<<endl;
	cout<<endl;

	cout<<"测试数据为正序："<<endl;
	int quick1[10]={10,20,30,40,50,60,70,80,90,100};
	cout<<"排序前："<<endl;
	for(i=1;i<10;i++)
		cout<<quick1[i]<<' ';
	cout<<endl;
	QuickSort(quick1,0,9);
	cout<<"比较次数："<<compare<<endl;
	cout<<"移动次数："<<move<<endl;
	compare=0;
	move=0;
	cout<<"排序后："<<endl;
	for(i=1;i<10;i++)
		cout<<quick1[i]<<' ';
	cout<<endl;
	cout<<endl;

	cout<<"测试数据为逆序："<<endl;
	int quick2[10]={111,99,88,77,66,55,44,33,22,11};
	cout<<"排序前："<<endl;
	for(i=1;i<10;i++)
		cout<<quick2[i]<<' ';
	cout<<endl;
	QuickSort(quick2,0,9);
	cout<<"比较次数："<<compare<<endl;
	cout<<"移动次数："<<move<<endl;
	compare=0;
	move=0;
	cout<<"排序后："<<endl;
	for(i=1;i<10;i++)
		cout<<quick2[i]<<' ';
	cout<<endl;
	cout<<endl;

	cout<<"测试数据为随机数据："<<endl;
	srand((unsigned)time(NULL));
	int random[10];
	for(i=1;i<10;i++)
		random[i]=rand()%20;
	cout<<"排序前："<<endl;
	for(i=1;i<10;i++)
		cout<<random[i]<<' ';
	cout<<endl;
	QuickSort(random,0,9);
	cout<<"比较次数："<<compare<<endl;
	cout<<"移动次数："<<move<<endl;
	compare=0;
	move=0;
	cout<<"排序后："<<endl;
	for(i=1;i<10;i++)
		cout<<random[i]<<' ';
	cout<<endl;
	cout<<endl;

	cout<<"快速排序结束。"<<endl;
	cout<<endl;
}

/*#include<iostream>
#include<ctime>
using namespace std;

//(只要有哨兵)数组的第一个元素就不参与到排序中，换言之测试数据的第一个记录不参与排序
//不过插入排序的正序排列因为不移动元素所以无上情况
//有类似情况的：插入排序；希尔排序；冒泡排序；简单选择排序
//快速排序有问题！


//快速排序
//快速排序一次划分函数
int Partition(int r[],int low,int high)
{
	r[0]=r[low];
	while(low<high)
	{
		while(low<high&&r[high]>=r[0])
			--high;
		r[low]=r[high];

		while(low<high&&r[low]<=r[0])
			++low;
		r[high]=r[low];
	}
	r[low]=r[0];
	return low;
}
//快速排序非递归函数
void QuickSort(int r[],int n)
{
	int top=-1;//顺序栈并假设无上溢
	int low=0,high=n-1;
	int i,s[20];
	while(low<high||top!=-1)
	{
		while(low<high)
		{
			i=Partition(r,low,high);//一次划分
			s[++top]=i;//入栈
			high=i-1;//high指向左半序列最末记录
		}
		if(top!=-1)
		{
			i=s[top--];//出栈
			low=i+1;//low指向右半序列起始记录
		}
	}
}



void main()
{
	int i;

	cout<<"快速排序测试:"<<endl;
	cout<<endl;

	cout<<"测试数据为正序："<<endl;
	int quick1[10]={10,20,30,40,50,60,70,80,90,100};
	cout<<"排序前："<<endl;
	for(i=1;i<10;i++)
		cout<<quick1[i]<<' ';
	cout<<endl;
	QuickSort(quick1,10);
	cout<<"排序后："<<endl;
	for(i=1;i<10;i++)
		cout<<quick1[i]<<' ';
	cout<<endl;
	cout<<endl;

	cout<<"测试数据为逆序："<<endl;
	int quick2[10]={111,99,88,77,66,55,44,33,22,11};
	cout<<"排序前："<<endl;
	for(i=1;i<10;i++)
		cout<<quick2[i]<<' ';
	cout<<endl;
	QuickSort(quick2,10);
	cout<<"排序后："<<endl;
	for(i=1;i<10;i++)
		cout<<quick2[i]<<' ';
	cout<<endl;
	cout<<endl;

	cout<<"测试数据为随机数据："<<endl;
	srand((unsigned)time(NULL));
	int random[10];
	for(i=1;i<10;i++)
		random[i]=rand()%20;
	cout<<"排序前："<<endl;
	for(i=1;i<10;i++)
		cout<<random[i]<<' ';
	cout<<endl;
	QuickSort(random,10);
	cout<<"排序后："<<endl;
	for(i=1;i<10;i++)
		cout<<random[i]<<' ';
	cout<<endl;
	cout<<endl;

	cout<<"快速排序结束。"<<endl;
	cout<<endl;
}*/